// 找二叉树中两个节点的寻公共祖先
// ----------------------可以用栈存储一个二叉树节点的路径---------------------------
#include <iostream>
#include <stack>

struct TreeNode
{
    int val = 0;
    TreeNode *left = nullptr;
    TreeNode *right = nullptr;
};

class Solution
{
    bool findNodePath(TreeNode *root, TreeNode *node, std::stack<TreeNode *> &st)
    {
        if (root == nullptr)
            return false;

        // 入栈
        st.push(root);
        // 判断是否是要找的元素
        if (root == node)
            return true;
        // 递归
        if (findNodePath(root->left, node, st))
            return true;
        if (findNodePath(root->right, node, st))
            return true;

        // 如果该节点的左右子树都递归的到空了，就说明不在该子树中，该路径不对，所以将该元素pop
        st.pop();
        return false;
    }

public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        std::stack<TreeNode *> st_p_path;
        std::stack<TreeNode *> st_q_path;

        // 寻找路径
        findNodePath(root, p, st_p_path);
        findNodePath(root, q, st_q_path);

        // 让他们的长度先一致
        while (st_p_path.size() != st_q_path.size())
        {
            if (st_p_path.size() > st_q_path.size())
                st_p_path.pop();
            else
                st_q_path.pop();
        }
        // 一起pop找相同的位置
        while (st_p_path.top() != st_q_path.top())
        {
            st_p_path.pop();
            st_q_path.pop();
        }

        return st_p_path.top();
    }
};